/*
 * Copyright (C) 2025 Tsingteng MicroSystem
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
#include "priority_queue.h"
#include "stdbool.h"
#include "nfc_osi_api.h"
#include "nfc_log_api.h"

/**
 * @file priority_queue.c
 * @brief 优先级队列单向链表实现
 * @date 2024-04-11
*/

/**
 * @brief 创建节点
 *
 * 根据给定的优先级队列、数据、优先级和标签，创建一个新的节点，并将其指针返回。
 *
 * @param queue 优先级队列指针
 * @param data 数据指针
 * @param priority 优先级
 * @param tag 标签
 *
 * @return 创建的节点指针，如果队列为空则返回 NULL
 */
static tQUEUE_NODE *create_node(tPRIORITY_QUEUE *queue, void* data, tQUEUE_PRIORITY priority, tQUEUE_TAG tag) {
    if (queue == NULL) {
        return NULL;
    }
    tQUEUE_NODE *node = osi_calloc(sizeof(tQUEUE_NODE));
    if (node != NULL) {
        node->data = data;
        node->priority = priority;
        node->next = NULL;
        node->id = ++(queue->base_id);
        node->tag = tag;
    }
    return node;
}
/**
 * @brief 释放节点
 *
 * 释放指定的节点，并可选择是否释放节点的数据。
 *
 * @param queue 优先级队列指针
 * @param node 节点指针
 * @param free_data 是否释放节点数据
 */
static void free_node(tPRIORITY_QUEUE *queue, tQUEUE_NODE *node, bool free_data) {
    if (node == NULL) {
        return;
    }
    if (queue != NULL && queue->cleanup != NULL && free_data) {
        queue->cleanup(node->id, node->tag, node->data);
    }
    osi_free(node);
    if (queue->size > 0) {
        queue->size--;
    }
}

/**
 * @brief 默认清理函数
 *
 * 当队列项不再需要时，调用此函数进行清理。
 *
 * @param id 队列ID
 * @param tag 队列标签
 * @param data 队列项数据指针
 */
void pq_default_cleanup(tQUEUE_ID id, tQUEUE_TAG tag, void *data) {
    (void) id;
    (void) tag;
    if (data != NULL) {
        osi_free(data);
    }
}

/**
 * @brief 优先级队列提供的默认最小优先级对比函数
 *
 * 用于实现最小优先级队列。
 *
 * @param inserted 被插入队列的元素的优先级
 * @param compared 要比较的元素的优先级
 *
 * @return 1.当被插入元素的优先级满足插入条件时，返回大于0的数
 *         2.当被插入元素的优先级不满足插入条件时，返回小于0的数
 *         3.当被插入元素的优先级和队列中元素的优先级相等时，返回0
 */
int64_t pq_comp_min(tQUEUE_PRIORITY inserted, tQUEUE_PRIORITY compared) {
    return compared - inserted;
}

/**
 * @brief 优先级队列提供的默认最大优先级对比函数
 *
 * 用于实现最小优先级队列。
 *
 * @param inserted 被插入队列的元素的优先级
 * @param compared 要比较的元素的优先级
 *
 * @return 1.当被插入元素的优先级满足插入条件时，返回大于0的数
 *         2.当被插入元素的优先级不满足插入条件时，返回小于0的数
 *         3.当被插入元素的优先级和队列中元素的优先级相等时，返回0
 */
int64_t pq_comp_max(tQUEUE_PRIORITY inserted, tQUEUE_PRIORITY compared) {
    return inserted - compared;
}

/**
 * @brief 初始化优先级队列
 *
 * 初始化给定的优先级队列，并使用给定的比较函数和清理函数。
 * @note 初始化后，队列为空。
 * @note 传入的queue必须是未初始化过的队列，否则会导致内存泄漏。
 *
 * @param comp 比较函数指针
 * @param cleanup 清理函数指针
 *
 * @return 初始化成功返回 true，否则返回 false
*/
bool pq_init(tPRIORITY_QUEUE *queue, tQUEUE_COMP comp, tQUEUE_CLEANUP cleanup) {
    if (NULL == queue) {
        return false;
    }
    queue->comp = comp;
    queue->cleanup = cleanup;
    queue->root = NULL;
    queue->size = 0;
    queue->base_id = 0;
    return true;
}

/**
 * @brief 销毁优先级队列
 *
 * 销毁给定的优先级队列，并释放相关资源。
 *
 * @note 可以通过free_data参数控制是否释放队列中数据的内存。但是不会释放队列本身的内存，即queue指针对应的内存。
 *
 * @param queue 优先级队列指针
 * @param free_data 是否释放队列中数据的内存
 *
 * @return 如果销毁成功，则返回 true；否则返回 false
 */
bool pq_deinit(tPRIORITY_QUEUE* queue, bool free_data) {
    if (queue == NULL) {
        return false;
    }

    pq_clear(queue, free_data);

    queue->comp = NULL;
    queue->cleanup = NULL;
    return true;
}
/**
 * @brief 将数据加入优先级队列
 *
 * 将给定的数据加入优先级队列中，并根据优先级和标签进行排序。
 *
 * @param queue 优先级队列指针
 * @param data 数据指针
 * @param priority 优先级
 * @param tag 标签
 * @param id 节点ID指针
 *
 * @return 成功返回true，否则返回false
 */
bool pq_enqueue(tPRIORITY_QUEUE* queue, void* data, tQUEUE_PRIORITY priority, tQUEUE_TAG tag, tQUEUE_ID *id) {
    if (queue == NULL || queue->comp == NULL) {
        return false;
    }
    tQUEUE_NODE *node = create_node(queue, data, priority, tag);
    if (node == NULL) {
        return false;
    }

    tQUEUE_NODE *curr = queue->root;
    if (curr == NULL || queue->comp(node->priority, curr->priority) > 0) {
        queue->root = node;
        queue->root->next = curr;
    } else {
        while (curr->next != NULL && queue->comp(node->priority, curr->next->priority) <= 0) {
            curr = curr->next;
        }
        tQUEUE_NODE *temp_next = curr->next;
        curr->next = node;
        curr->next->next = temp_next;
    }
    queue->size++;
    if (id != NULL) {
        *id = node->id;
    }
    return true;
}
/**
 * @brief 从优先级队列中出队
 *
 * 从给定的优先级队列中移除并返回队首元素。
 *
 * @param queue 优先级队列指针
 *
 * @return 队首元素指针，如果队列为空或指针为NULL则返回NULL
 */
void *pq_dequeue(tPRIORITY_QUEUE* queue) {
    if (queue == NULL || queue->size == 0) {
        return NULL;
    }

    tQUEUE_NODE *first = queue->root;
    void* data = NULL;

    if (first != NULL) {
        queue->root = first->next;
        data = first->data;
        free_node(queue, first, false);
    }
    return data;
}

/**
 * @brief 从优先级队列中移除指定 ID 的节点
 *
 * 从给定的优先级队列中移除指定 ID 的节点，并返回该节点的数据指针。
 *
 * @param queue 优先级队列指针
 * @param id 要移除的节点的 ID
 *
 * @return 成功移除的节点的数据指针，若未找到则返回 NULL
 */
void* pq_remove(tPRIORITY_QUEUE *queue, tQUEUE_ID id) {
    if (queue == NULL || queue->size == 0) {
        return NULL;
    }
    tQUEUE_NODE *curr = queue->root;
    if (curr == NULL) {
        return NULL;
    }
    void *data = NULL;
    if (curr->id == id) {
        queue->root = curr->next;
        data = curr->data;
        free_node(queue, curr, false);
    } else {
        while (curr->next != NULL && curr->next->id != id) {
            curr = curr->next;
        }
        if (curr->next != NULL && curr->next->id == id) {
            data = curr->next->data;
            tQUEUE_NODE *next_next = curr->next->next;
            free_node(queue, curr->next, false);
            curr->next = next_next;
        }
    }
    return data;
}

/**
 * @brief 从优先级队列中删除所有指定TAG的节点
 *
 * 从给定的优先级队列中删除所有具有指定TAG的节点，并返回被删除节点的数量。
 *
 * @param queue 优先级队列指针
 * @param tag 指定TAG
 * @param free_data 是否释放节点数据
 *
 * @return 被删除节点的数量
 */
size_t pq_remove_all(tPRIORITY_QUEUE *queue, tQUEUE_TAG tag, bool free_data) {
    size_t remove_count = 0;
    if (queue == NULL || queue->root == NULL) {
        return remove_count;
    }

    tQUEUE_NODE *root = queue->root;

    // find first not match
    while (root != NULL && root->tag == tag) {
        tQUEUE_NODE *next_root = root->next;
        free_node(queue, root, true);
        root = next_root;
        remove_count++;
    }
    queue->root = root;

    if (queue->root == NULL) {
        return remove_count;
    }

    tQUEUE_NODE *curr = queue->root;
    tQUEUE_NODE *next = curr->next;

    while (next != NULL) {
        tQUEUE_NODE *next_next = next->next;

        if (next->tag == tag) {
            free_node(queue, next, free_data);
            curr->next = next_next;
            remove_count++;
        } else {
            curr = next;
        }
        next = next_next;
    }

    return remove_count;
}

/**
 * @brief 遍历优先级队列
 *
 * 遍历给定的优先级队列，对每个元素执行指定的回调函数。
 *
 * @param queue 优先级队列指针
 * @param foreach 回调函数指针
 *
 * @return 遍历的元素数量
 */
size_t pq_foreach(tPRIORITY_QUEUE *queue, tQUEUE_FOREACH foreach) {
    size_t index = 0;
    if (queue == NULL || foreach == NULL) {
        return index;
    }

    tQUEUE_NODE *curr = queue->root;

    while (curr != NULL) {
        if (!foreach(index, curr->id, curr->tag, curr->priority, (const void*) curr->data)) {
            index++;
            break;
        }
        index++;
        curr = curr->next;
    }

    return index;
}

/**
 * @brief 清空优先级队列
 *
 * 清空给定的优先级队列，并释放队列中的节点内存。
 *
 * @param queue 优先级队列指针
 * @param free_data 是否释放节点数据内存
 *
 * @return 成功删除的节点数量
 */
size_t pq_clear(tPRIORITY_QUEUE *queue, bool free_data) {
    size_t count = 0;
    if (queue == NULL) {
        return count;
    }

    tQUEUE_NODE *curr = queue->root;

    while (curr != NULL) {
        tQUEUE_NODE *next = curr->next;
        free_node(queue, curr, free_data);
        count++;
        curr = next;
    }

    queue->root = NULL;
    queue->size = 0;

    return count;
}
